package io.github.hadyang.leetcode.offer;

import java.util.Arrays;
import org.junit.Test;

/** @author haoyang.shi */
public class Duplicate {

  @Test
  public void test() {
    int[] duplication = new int[1];
    duplicate(new int[] {2, 3, 1, 0, 2, 5, 3}, 0, duplication);

    System.out.println(Arrays.toString(duplication));
  }

  // Parameters:
  //    numbers:     an array of integers
  //    length:      the length of array numbers
  //    duplication: (Output) the duplicated number in the array number,length of duplication array
  // is 1,so using duplication[0] = ? in implementation;
  //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in
  // C/C++
  //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
  // Return value:       true if the input is valid, and there are some duplications in the array
  // number
  //                     otherwise false
  public boolean duplicate(int numbers[], int length, int[] duplication) {
    if (numbers == null || numbers.length == 0) return false;

    for (int i = 0; i < numbers.length; i++) {

      while (numbers[i] != i) {
        int number = numbers[i];
        int wrongNum = numbers[number];
        if (number == wrongNum) {
          duplication[0] = number;
          return true;
        }

        swap(numbers, i, number);
      }
    }

    return false;
  }

  private static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}
